1. Technical Field
The present invention relates in general to a system and method for delaying a priority boost for a processing thread. More particularly, the present invention relates to a system and method to boost certain threads only when the thread is about to be preempted.
2. Description of the Related Art
Modern computer systems perform multiple tasks seemingly at the same time. Using multitasking, the processor handles instructions from multiple processes by servicing the processes in a round-robin fashion. In this manner, a process is executed by the processor for a small amount of time before it is time sliced, it's settings and register values saved, a different process is executed by the processor. These processes, or “threads,” are a stream of instructions corresponding to one or more software applications that require handling by the processor. The terms “process” and “thread” are used herein interchangeably to note a stream of executable instructions that is executed by a processor. By quickly moving from one process to the next, it appears that each process is executed simultaneously.
The operating system regulates access to the processor. Most operating systems employ priority-based scheduling algorithms for this purpose. Priorities are assigned to programs according to the importance and/or urgency of the functions that are performed on behalf of the computer system. The operating system uses these priorities to determine when and for how long a process or unit of executable code within the programs (hereafter, “thread” or “process”) is granted access to the processor. Generally, priority-based scheduling allocates processor time to optimize the computer system's performance. For example, the computer system may be optimized in order to minimize user input response time, maximize throughput, and/or guarantee predictable, or deterministic, execution times for application programs.
Many resources within a computer system are shared by the various programs being executed by the processor. In many cases, these resources need to be serialized so that only one process is using the resource in any given time. In order to serialize access to the resource, software locks are often used. When a resource is being used by another process, a process will wait on the lock. When the lock is released by the other process, the process will attempt to acquire the lock. Other processes will be unable to use the resource until the process releases the lock. Because of this serialization, efficient use of shared resources helps improve overall system throughput. This is especially true of resources and corresponding locks that are used by many processes.
In an operating system using a priority-based scheduling algorithm, a process with an inferior priority may be preempted by a process of the superior priority. This is true even when the inferior priority process currently possesses a critical resource. To address this problem, a thread will often request a priority boost, or increase, before entering a critical section of code during which the thread will often be using a shared resource controlled by a lock. When the thread is finished with the critical section of code, the lock is released and the thread's priority is reset (un-boosted) by the operating system. A challenge of this approach, however, is that the thread takes time to request the priority level changes (both to boost and un-boost) and also requires the services of and further burdens the operating system. This time is taken even though, in many situations, the thread would not have been preempted even if its priority had not been changed. However, many processes cannot risk the chance that their thread will be preempted during a critical section, so the process boosts and un-boosts the thread's priority.
FIG. 1 is a high level flowchart showing how priority boosts are handled in prior art systems when a thread enters a critical section. User thread processing commences at 100 whereupon, at some point, the user thread prepares to enter a critical section of code and requests a priority boost (step 110) to reduce the chances of the thread being preempted while performing the critical section. Kernel processing (i.e., the scheduler) commences at 120 whereupon, at step 130, the kernel process receives the priority boost request from the user thread and updates priority data structure 140 accordingly.
Upon receiving the priority boost, the user thread performs the critical section at step 150. After the critical section is completed, the user thread prepares to exit the critical section and, at step 160, requests that its priority be reset to its normal level. User processing thereafter ends at 180.
Kernel process 120 receives the second priority change request from the user thread at step 170 and updates thread data structures included in priority data 140 accordingly. Kernel processing thereafter ends at 190.
As can be seen by the processing shown in FIG. 1, the user thread made two requests to the kernel process in order to boost and, subsequently, reset its priority. If no other threads would have preempted the user thread during performance of the critical section, then both requests to the kernel process were not needed. However, a not inconsequential number of times, the user thread may have been preempted, so in the prior art the user thread is forced to make such requests of the kernel process to guard against being preempted. In addition, preemption often occurs as a result of time-slicing whereupon the waiting thread has the same priority (i.e., another user thread) as the thread currently running on the CPU. Preemption in favor of another thread with the same priority indicates that even a small priority boost is helpful for the currently-running thread to complete processing the critical section. However, even a small priority boost is costly in terms of the user level thread having to make two kernel process requests and the kernel process needing to handle both requests.
What is needed, therefore, is a system and method for delaying the priority boost of a thread until such time as the thread is about to be preempted. What is further needed is a system and method for limiting requests made by a thread to a kernel process to boost and reset its priority.